package suanfa;

public class BS_LeftTest1 {

    public static void main(String[] args) {
        int[] arr = new int[]{3, 5, 10, 11, 18, 45};
        int index = bsFind(arr, 16);
        if (index > -1) {
            System.out.println("位置：" + index);
        } else {
            System.out.println("未找到数据");
        }
    }

    static final int MAXIMUM_CAPACITY = 1 << 30;

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    private static int bsFind(int[] arr, int num) {
        int L = 0, R = arr.length - 1;
        int findIdx = -1;
        while (findIdx == -1) {
            int idx = (L + R) / 2;
            if (arr[idx] >= num) {
                if (R == L) {
                    findIdx = idx;
                } else {
                    R = idx;
                }
            } else {
                L = idx + 1;
            }
            //当出现R位置比L位置还小或等于L位置时
            //则已经搜索完成也没找到数据
            if (R < L) {
                break;
            }
        }
        return findIdx;
    }
}
